/*
 * Edit Distance
 * DP
 *  (c) 2007 Happy Yellow
 * test case
  var a= 'abcdefghijklmnopqrstuvwxyzlmnopqrstuvwxyzlmnopqrstuvwxyzlmnopqrstuvwxyzlmnopqrstuvwxyz',
  b = 'bcedhfgkjilmnopqrstuvwxyzlmnopqrstuvwxyzlmnopqrstuvwxyzlmnopqrstuvwxyzlmnopqrstuvwxyz';
  alert(EditDistance(a,b,10));
*/

function EditDistance(s1, s2, limit){
	var len1 = s1.length, len2 = s2.length;
	if(limit == null)
		limit = len1+len2;
	else if(Math.abs(len1-len2)>=limit)
		return limit;
	var a, b, a1 = new Array(len2+1), a2 = new Array(len2+1);
	//var o=0;
	for(var j=0; j<=len2; j++)
		a2[j] = j;
	for(var i=1; i<=len1; i++){
		a = a1;
		a1 = a2;
		a2 = a;
		a2[0] = i;
		a = i-limit;
		b = i+limit;
		if(a>0)
			a2[a] = limit;
		else
			a = 0;
		for(var j=a+1; j<=len2; j++){
			//o++;
			if(j>=b){
				a2[j] = limit;
				break;
			}
			a = a1[j-1];
			if(s1[i-1] != s2[j-1])
				a++;
			a2[j] = Math.min(a, a2[j-1]+1, a1[j]+1);
		}
	}
	//log(o);
	return a2[len2];
}

function SimilarFragment(s1, s2, rate, lengthLimit){
	if(rate<=0 || rate>=1)
		throw new Error('Out of rate range!');
	var len = 0, n = Math.min(s1.length, s2.length, lengthLimit || Number.MAX_VALUE), a, b, a1 = new Array((n+1)*2), a2 = new Array((n+1)*2), index = 1, ret = [], last = 0;
	a2[n] = 0;
	for(var i=1; len < n; i++){
		len = Math.min(i/rate, n);
		var ij = [-1,-1];
		ij.rate = rate;
		while(index<=len){
			a = a1;
			a1 = a2;
			a2 = a;
			a2[n-index] = index;
			a2[n+index] = index;
			var i1 = index-1, i2;
			b = false;
			for(var j=i1; j>0; j--){
				i2 = i1-j;

				a = a1[n-j];
				if(s1[i2] != s2[i1])
					a++;
				a2[n-j] = a = Math.min(a, a1[n-j+1]+1, a2[n-j-1]+1);
				if(a<=i){
					b = true;
					a = a/index;
					if(a<=ij.rate){
						ij.rate = a;
						ij[0] = i2;
						ij[1] = i1;
					}
				}

				a = a1[n+j];
				if(s1[i1] != s2[i2])
					a++;
				a2[n+j] = a =Math.min(a, a1[n+j-1]+1, a2[n+j+1]+1);
				if(a<=i){
					b = true;
					a = a/index;
					if(a<=ij.rate){
						ij.rate = a;
						ij[0] = i1;
						ij[1] = i2;
					}
				}
			}
			a = a1[n];
			if(s1[i1] != s2[i1])
				a++;
			a2[n] = a = Math.min(a, a2[n-1]+1, a2[n+1]+1);
			if(a<=i){
				b = true;
				a = a/index;
				if(a<=ij.rate){
					ij.rate = a;
					ij[0] = i1;
					ij[1] = i1;
				}
			}
			if(!b && index>=last*2){
				len = null;
				break;
			}
			else
				last = index;
			index++;
		}
		if(len == null)
			break;
		if(ij.rate<rate)
			ret.push(ij);
	}
	if(ret.length == 0)
		return null;
	//ret.each(function(it, i){log('ret['+i+']='+it+'('+it.rate+')');});
	a = ret.pop();
	a1 = Math.max(a[0], a[1]);
	while(ret.length>0){
		b = ret.pop();
		a2 = Math.max(b[0], b[1]);
		if((a1*a.rate - a2*b.rate).toFixed() == a1 - a2){
			a1 = a2;
			a = b;
		}
		else
			break;
	}
	return a;
}
